#ifndef __LAZY_LIST__H
#define __LAZY_LIST__H

#include "cpp_framework.h"

using namespace CMDR;

template<typename T>
class LazyList {
private:
	class Node : public HazardMemory::Object {
	public:
		const T          _item;
		AtomicMarkableReference<Node>	_next;
		CMDR::TTASLock						_lock;

		Node(const T& item) : _item(item), _next(null, false) { }
		Node(const T& item, Node* const next) : _item(item), _next(next, false) { }

		virtual ~Node() {;}

		virtual bool isValid() { 
			return (false == _next.isMarked());
		}

		virtual HazardMemory::Object* getNextValid(const int indx) {
			return _next.getReference();
		}

		virtual HazardMemory::Object* getNextValid(const int indx, int& stamp) {
			bool tmpStamp;
			HazardMemory::Object* tmpPtr = _next.get(&tmpStamp);
			if(tmpStamp) stamp = 1; else stamp=0;
			return tmpPtr;
		}

		void Lock()  { _lock.lock(); }
		void UnLock() { _lock.unlock(); }
	};

private:
	VolatileType<Node*>	_head;
	SnapshotCounter		_counter;

public:

	LazyList(int numOfThreads) : _counter(numOfThreads) {
		Node* tail = new Node(Integer::MAX_VALUE, null);
		_head = new Node (Integer::MIN_VALUE, tail);
	}

	~LazyList() {
		//we assume no one access the object at this point.
		Node* pCurr = _head;
		Node* next = null;
		while(null != pCurr) {
			next = pCurr->_next.getReference();
			delete pCurr;
			pCurr = next;
		}
	}

	bool contains(const T& item, int threadID) {
		HazardMemory::Ptr<Node> pPred;
		HazardMemory::Ptr<Node> pCurr;
		pPred = _head;
		pCurr.extractNext(pPred, 0);
		while (pCurr->_item < item) {
			pPred = pCurr;
			pCurr.extractNext(pPred, 0);
		}
		return (pCurr->_item == item && pCurr->isValid());
	}

	bool remove(const T& item, int threadID) {
		HazardMemory::Ptr<Node> pPred;
		HazardMemory::Ptr<Node> pCurr;

		while (true) {
			pPred = _head;
			pCurr.extractNext(pPred, 0);
			while (pCurr->_item < item) {
				pPred = pCurr;
				pCurr.extractNext(pPred, 0);
			}

			pPred->Lock(); 
			pCurr->Lock();
			if (validate(pPred, pCurr)) {
				if (pCurr->_item != item) {
					pCurr->UnLock();
					pPred->UnLock();
					return false;
				} else {
					pPred->_next.set(pCurr->_next.getReference(), false);
					pCurr->_next.set(pCurr->_next.getReference(), true);
					_counter.dec(threadID);
					pCurr->UnLock();
					pPred->UnLock();
					return true;
				}
			}
			pCurr->UnLock();
			pPred->UnLock();
		} 
	}

	bool add(const T& item, int threadID) {
		HazardMemory::Ptr<Node> pPred;
		HazardMemory::Ptr<Node> pCurr;
	
		while (true) {
			pPred = _head;
			pCurr.extractNext(pPred, 0);
			while (pCurr->_item < item) {
				pPred = pCurr;
				pCurr.extractNext(pPred, 0);
			}

			pPred->Lock(); 
			pCurr->Lock();

			if (validate(pPred, pCurr)) {
				if (pCurr->_item == item) {
					pCurr->UnLock();
					pPred->UnLock();
					return false;
				} else {
					std::auto_ptr<Node> newNode(new Node(item, pCurr.getReference()));
					pPred->_next.set(newNode.get(), false);
					newNode.release();
					_counter.inc(threadID);
					pCurr->UnLock();
					pPred->UnLock();
					return true;
				}
			}

			pCurr->UnLock();
			pPred->UnLock();
		} 
	}

	void clean(int threadID) {
		HazardMemory::Ptr<Node> head;
		HazardMemory::Ptr<Node> pCurr;
		HazardMemory::Ptr<Node> pSucc;
		head = _head;
		head->Lock();
		pCurr.extractNext(head, 0);
		while(pCurr->_item < Integer::MAX_VALUE) {
			pCurr->Lock();
			pSucc.extractNext(pCurr,0);
			head->_next.set(pSucc.getReference(), false);
			if(pCurr->_next.compareAndSet(pSucc.getReference(), pSucc.getReference(), false, true)) {
				pCurr.retire();
				_counter.dec(threadID);
			}
			pCurr->UnLock();
			pCurr.extractNext(head, 0);
		}
		head->UnLock();
	}
	
	bool isEmpty(int threadID) {
		return _counter.scan() == 0;
	}
	int size(int threadID){
		return _counter.scan();
	}

private:
	bool validate(HazardMemory::Ptr<Node>& pPred, HazardMemory::Ptr<Node>& pCurr) {
		//assume both "pPred" & "pCurr" locked and can not change during this test
		if (pPred->isValid() && pCurr->isValid() && pPred->_next.getReference() == pCurr.getReference())
			return true;
		else
			return false;
	}
}; 

#endif // __LAZY_LIST__H